package formal.linkedList;

import java.util.Stack;

/**
 * 删除链表的倒数第N个节点
 *
 * @author DengYuan2
 * @create 2021-01-07 19:26
 */
public class M_19 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
//        n1.next = n2;
//        n2.next = n3;
//        n3.next = n4;
//        n4.next = n5;
//        ListNode listNode = removeNthFromEnd(n1, 1);
//        System.out.println(listNode);
        ListNode remove = removeNthFromEnd(n1, 1);
        System.out.println(remove);
    }

    /**
     * 我的原来写法：递归，但是存在问题，即没法删除第一个节点
     * 于是利用新的节点，指向当前的头节点！！见下面的remove方法
     */
    public static int no = 0;

    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        head.next = removeNthFromEnd1(next, n);
        no++;
        if (no == n) {
            head.next = next.next;
        }
        return head;
    }

    /**
     * 改进后的写法
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode remove(ListNode head, int n) {
        ListNode tmp = new ListNode(-1);
        tmp.next = head;
        return removeNthFromEnd1(tmp, n).next;
    }

    /**
     * 官方-计算链表长度，找到第length-n+1个节点进行删除
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dumNode = new ListNode(-1);
        dumNode.next = head;
        ListNode tmp = head;
        int length = 0;
        while (tmp != null) {
            length++;
            tmp = tmp.next;
        }
        ListNode pre = dumNode;
        ListNode cur = dumNode.next;
        for (int i = 1; i < length - n + 1; i++) {
            pre = pre.next;
            cur = pre.next;
        }
        pre.next = cur.next;
        return dumNode.next;
    }

    /**
     * 官方-栈
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd3(ListNode head, int n) {
        //哑节点
        ListNode dumNode = new ListNode(-1);
        dumNode.next=head;
        ListNode tmp = dumNode;
        Stack<ListNode> stack = new Stack<>();
        while (tmp != null) {
            stack.push(tmp);
            tmp = tmp.next;
        }
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        tmp = stack.peek();
        tmp.next=tmp.next.next;
        return dumNode.next;
    }

    /**
     * 官方-双指针
     * first到达末尾(null),second的下一个即为要删除的节点，first与second相隔n（即两节点之间有n个节点）
     * 看图更易理解：
     * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd4(ListNode head, int n){
        //因为是要删除节点，所以最好每个节点前面有节点，故要有哑节点
        ListNode dumNode = new ListNode(-1);
        dumNode.next=head;
        ListNode second = dumNode;
        ListNode first =head;
        for (int i = 0; i < n; i++) {
            first=first.next;
        }
        while (first!=null){
            second=second.next;
            first=first.next;
        }
        second.next=second.next.next;
        return dumNode.next;
    }

    /**
     *大神的写法，类似于方法4，但没有4好理解，未仔细看
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        while (n-- > 0) {
            fast = fast.next;
        }
        if (fast == null) {
            return head.next;
        }
        ListNode slow = head;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}
